/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */


/*
  // 数组保存 O(n) O(n)
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> list ;
        // 遍历将链表值放入数组通过下标寻找中间节点
        while(head != nullptr){
            list.push_back(head);  
            head = head->next;  
        }
             
        return list[list.size()/2];
    }
*/

/*
  // 指针遍历 O(n) O(1)
    ListNode* middleNode(ListNode* head) {
        ListNode* cur = head;
        size_t size = 0;
        while(cur != nullptr){
            ++size;
            cur = cur->next;
        } 
        int n = size / 2;
        while(n--){
            head = head->next;
        }
        return head;
    }
*/

  // 快慢指针 O(n) O(1)
   ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
      
        // 当fast走到nullptr时候,slow所在就是所求节点
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;  // 快指针每次走两步
            slow = slow->next; // 慢指针走一步
        }
        return slow;
    }
